/**
 * <vendor>
 *  Copyright 2009 Quanben Tech.
 * </vendor>
 */

using System;
using System.Text;
using System.Collections.Generic;
using QSharp.String.Compiler;


namespace QSharp.String.Rex
{
    public class ContinuousCharToken : CharToken, IContinuous<ContinuousCharToken>
    {
        public ContinuousCharToken(char ch) : base(ch)
        {
        }

        public ContinuousCharToken(CharToken ct) : base(ct.GetChar())
        {
        }

        public int CompareTo(ContinuousCharToken that)
        {
            return base.CompareTo(that);
        }

        public bool IsAdjacentTo(ContinuousCharToken that)
        {
            return IsSucceeding(that) || IsPreceding(that);
        }

        public bool IsSucceeding(ContinuousCharToken that)
        {
            return myCh == that.myCh + 1;
        }

        public bool IsPreceding(ContinuousCharToken that)
        {
            return myCh + 1 == that.myCh;
        }
    }

    public class CharSet
    {
        public static char LargestChar = (char)0xffff;
        protected bool mExclusive;
        protected SegmentedSet<ContinuousCharToken> mInnerSet 
            = new SegmentedSet<ContinuousCharToken>();

        public CharSet(bool bExclusive)
        {
            mExclusive = bExclusive;
        }

        public bool Contains(char ch)
        {
            ContinuousCharToken cct = new ContinuousCharToken(ch);
            bool bBaseContains = mInnerSet.Contains(cct);
            if (mExclusive) return !bBaseContains;
            else return bBaseContains;
        }

        public bool IsEmpty
        {
            get 
            {
                if (mExclusive)
                {
                    if (mInnerSet.SegmentCount != 1) return false;
                    if (mInnerSet[0].Low.GetChar() != '\0') return false;
                    if (mInnerSet[0].High.GetChar() != LargestChar) return false;
                    return true;
                }
                else
                {
                    return mInnerSet.IsEmpty;
                }
            }
        }

        public void Add(char ch)
        {
            mInnerSet.Add(new ContinuousCharToken(ch));
        }

        public void AddRange(char low, char high)
        {
            mInnerSet.AddRange(new ContinuousCharToken(low), new ContinuousCharToken(high));
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            if (mExclusive)
            {
                sb.Append('~');
            }

            sb.Append('(');
            sb.Append(mInnerSet.ToString());
            sb.Append(')');

            return sb.ToString();
        }
    }   /* class CharSet */

    /**
     * <summary>
     *  The entity used to create a regular machine out of a pattern stream
     * </summary>
     */
    public class Creator<Stream, Token>
        where Stream : ICloneableStream
    {
    /* Exceptions */
        public class Exception : System.ApplicationException
        {
            public readonly int Pos;

            public Exception(int pos)
            {
                Pos = pos;
            }
        }

    /* Types in class Creator */

        protected enum CharSetState
        {
            NoChar,
            OneChar,
            Waiting
        }

        protected struct ParsingState
        {
            public Machine<Stream>.IState BeginNode;
            public Machine<Stream>.IState EndNode;
        }

        protected abstract class Arrow : Machine<Stream>.Arrow
        {
            public enum Type
            {
                Unkown,
                CommonChar,
                CharSetChar,
                Tag,
                AnyChar,
            }

            protected Machine<Stream>.IState mTarget = null;

            public override Machine<Stream>.IState Target
            {
                get
                {
                    return mTarget;
                }

                set
                {
                    mTarget = value;
                }
            }

            public virtual void Link(Machine<Stream>.IState begin, Machine<Stream>.IState end)
            {
                mTarget = end;
                begin.AddOutlet(this);
            }
        }


        /**
         * <summary> 
         *  Arrow type 1: Char-set arrow, which is associated with a char-set
         * </summary>
         */

        class CharSetArrow : Arrow
        {
            CharSet mCharSet;

            public CharSetArrow(CharSet cs)
            {
                mCharSet = cs;
            }

            public override Machine<Stream>.IState Go(Stream stream)
            {
                IToken token = stream.Read();
                CharToken ct = token as CharToken;
                if (ct == null)
                {
                    return null;
                }

                ContinuousCharToken cct = new ContinuousCharToken(ct);

                if (mCharSet.Contains(cct))
                {
                    stream.Move(1);
                    return mTarget;
                }
                else
                {
                    return null;
                }
            }

            public override string ToString()
            {
                StringBuilder sb = new StringBuilder("CharSetArrow with charset ");
                sb.Append(mCharSet.ToString());
                return sb.ToString();
            }
        }

        class AnyCharArrow : CharSetArrow
        {
            public AnyCharArrow() : base(new CharSet(true))
            {
            }
        }

        /**
         * <summary> 
         *  Arrow type 2: String arrow, which deals with plain text
         * </summary>
         */

        class StringArrow : Arrow
        {
            string mString;

            public StringArrow(string s)
            {
                mString = s;
            }

            public override Machine<Stream>.IState Go(Stream stream)
            {
                TokenStream.Position rsv = (TokenStream.Position)stream.Pos.Clone();
                for (int i = 0; i < mString.Length; i++)
                {
                    Char ch = mString[i];

                    IToken token = stream.Read();
                    CharToken ct = token as CharToken;

                    if (ct == null || ct.GetChar() != ch)
                    {
                        stream.Pos = rsv;
                        return null;
                    }
                    stream.Move(1);
                }

                return mTarget;
            }

            public override string ToString()
            {
                StringBuilder sb = new StringBuilder("StringArrow with string = \"");
                sb.Append(mString);
                sb.Append('"');
                return sb.ToString();
            }
        }

        class CharArrow : Arrow
        {
            Char mCh;

            public CharArrow(Char ch)
            {
                mCh = ch;
            }            

            public override Machine<Stream>.IState Go(Stream stream)
            {
                IToken token = stream.Read();
                CharToken ct = token as CharToken;
                if (ct == null)
                {
                    return null;
                }

                if (ct.GetChar() == mCh)
                {
                    stream.Move(1);
                    return mTarget;
                }
                else
                {
                    return null;
                }
            }

            public override string ToString()
            {
                StringBuilder sb = new StringBuilder("CharArrow with char = '");
                sb.Append(mCh);
                sb.Append('\'');
                return sb.ToString();
            }
        }


        /**
         * <summary> 
         *  Arrow type 3: Tag arrow, which deals with back-referencing
         * </summary>
         */
        class TagArrow : Arrow
        {
            public TagTracker Tag = null;

            public TagArrow(TagTracker tag)
            {
                Tag = tag;
            }

            public override Machine<Stream>.IState Go(Stream stream)
            {
                TokenStream.Position reserved = (TokenStream.Position)stream.Pos.Clone();

                ICloneableStream src = (ICloneableStream)stream.Clone();
                src.Pos = (TokenStream.Position)Tag.Start.Peek().Clone();

                for (; !src.Pos.Equals(Tag.End); src.Move(1), stream.Move(1))
                {
                    IComparableToken token1 = src.Read() as IComparableToken;
                    IComparableToken token2 = stream.Read() as IComparableToken;

                    if (token1 == null) throw new InvalidCastException();

                    if (token2 == null || token1.CompareTo(token2) != 0)
                    {
                        stream.Pos = reserved;
                        return null;
                    }
                }

                return mTarget;
            }

            public override string ToString()
            {
                StringBuilder sb = new StringBuilder("TagArrow with tag = '");
                sb.Append(Tag);
                sb.Append('\'');
                return sb.ToString();
            }
        }

    /* Variables of class Creator */

        protected TagMpper mTagMapper = new TagMpper();
        protected Stack<TagCreator> mTagStack = new Stack<TagCreator>();

        protected int mTagCount = 0;
        protected bool mUseNumericTag = false;

    /* Properties */

        public bool UseNumericTag
        {
            get
            {
                return mUseNumericTag;
            }
        }

    /* Constructor and Destructor */

        public Creator()
        {
        }

        public Creator(bool bNumericTag)
        {
            mUseNumericTag = bNumericTag;
        }

    /* Methods of class Creator */

        protected bool GetEscape(out Char ch, string s, ref int i, int end)
        {
            i++;    // skip '\\'
            ch = new Char();
            if (i >= end) return false;

            ch = s[i];
            if (ch == 'x')
            {
                char c;
                i++;

                int val = 0;
                for (int j = 0; j < 4; j++, i++)
                {
                    if (i >= end) return false;

                    int d;
                    c = s[i];
                    if (c >= '0' && c <= '9')
                        d = c - '0';
                    else if (c >= 'A' && c <= 'F')
                        d = c - 'A' + 10;
                    else if (c >= 'f' && c <= 'f')
                        d = c - 'a' + 10;
                    else
                        return false;
                    val <<= 4;
                    val |= d;
                }
                ch = (char)val;
            }
            else if (ch == 'n')
            {
                ch = '\n';
                i++;
            }
            else if (ch == 't')
            {
                ch = '\t';
                i++;
            }
            else
            {
                i++;
            }

            return true;
        }

        protected bool GetCharSet(out CharSet charset, string s, ref int i, int end)
        {
            i++;
            Char chCurr = new Char(), chLast = new Char();
            bool bExclusive = s[i] == '^';
            CharSetState state = CharSetState.NoChar;

            if (bExclusive)
            {
                i++;
            }

            charset = new CharSet(bExclusive);

            for (; i < end; i++)
            {
                if (s[i] == '\\')
                {
                    if (!GetEscape(out chCurr, s, ref i, end))
                        return false;
                }
                else if (s[i] == '-' && state == CharSetState.OneChar)
                {
                    state = CharSetState.Waiting;
                }
                else if (s[i] == ']')
                {
                    if (state == CharSetState.OneChar)
                    {
                        charset.Add(chLast);
                    }
                    else if (state == CharSetState.Waiting)
                    {
                        /* 
                         * actually a set closed with a trailing '-' is not an approved expression 
                         * and the '-' is treated verbatim
                         */
                        charset.Add(chLast);
                        charset.Add('-');
                    }
                    i++;
                    return !charset.IsEmpty;
                }
                else
                {   /* common characters */
                    chCurr = s[i];
                }

                if (state == CharSetState.NoChar)
                {
                    chLast = chCurr;
                    state = CharSetState.OneChar;
                }
                else if (state == CharSetState.OneChar)
                {
                    charset.Add(chLast);
                    chLast = chCurr;
                }
                else    /* state == CharSetState.Waiting */
                {
                    if (chLast > chCurr) break;
                    charset.AddRange(chLast, chCurr);
                    state = CharSetState.NoChar;
                }
            }

            return true;
        }

        protected bool GetIteration(out Machine<Stream>.Iteration iteration, string s, ref int i, int end)
        {
            iteration = new Machine<Stream>.Iteration();
            if (s[i] == '*')
            {
                iteration.AddRange(0, Machine<Stream>.Iteration.Infinity);
                i++;
                return true;
            }
            if (s[i] == '+')
            {
                iteration.AddRange(1, Machine<Stream>.Iteration.Infinity);
                i++;
                return true;
            }

            i++;    /* it must be '{', skip it */

            StringStream ss = new StringStream(s.Substring(i, end-i));

            uint low, high, high1;
            bool res = false;

            for (; !ss.IsEos(); )
            {
                Lexical.SkipBlanks(ss);

                if (ss.IsEos())
                {
                    break;
                }

                if (Lexical.ReadDec(out low, ss) == 0)
                {
                    break;
                }

                high1 = low;

                Lexical.SkipBlanks(ss);

                if (ss.IsEos())
                {
                    break;
                }

                CharToken ct = ss.Read() as CharToken;

                if (ct.GetChar() == '-')
                {
                    ss.Move(1);
                    Lexical.SkipBlanks(ss);

                    if (ss.IsEos())
                    {
                        break;
                    }

                    ct = ss.Read() as CharToken;

                    if (ct.GetChar() == '}')
                    {
                        high = Machine<Stream>.Iteration.Infinity;
                        iteration.AddRange(low, high);
                        ss.Move(1);
                        res = true;
                        break;
                    }
                    else if (Lexical.ReadDec(out high1, ss) > 0)
                    {
                        Lexical.SkipBlanks(ss);
                    }
                    else
                    {   // error
                        break;
                    }
                }

                ct = ss.Read() as CharToken;
                if (ct.GetChar() == ',')
                {
                    high = high1;
                    iteration.AddRange(low, high);
                    ss.Move(1);
                }
                else if (ct.GetChar() == '}')
                {
                    high = high1;
                    iteration.AddRange(low, high);
                    ss.Move(1);
                    res = true;
                    break;
                }
                else
                {
                    break;
                }
            }

            i += ((StringStream.Position)ss.Pos).ToInt();
            return res;
        }

        protected bool GetTag(out TagTracker tag, string s, ref int i, int end)
        {
            tag = null;

            // i is one character after "\k"
            i++;    // skip '<'
            int iTagNameBegin = i;

            for (; i < end && s[i] != '>'; i++)
            {
            }

            if (i >= end) return false;

            int iTagNameEnd = i;
            i++;

            string sTag = s.Substring(iTagNameBegin, iTagNameEnd - iTagNameBegin);

            TagCreator tagCreator = mTagMapper[sTag];

            if (tagCreator == null || !tagCreator.Closed)
            {
                i = iTagNameBegin - 3;
                return false;
            }

            tag = tagCreator.Tracker;

            return true;
        }

        /**
         * <summary>
         *  Connect beginNode and endNode with a path given by the s.Substring(i, end-i)
         *  which contains no brackets
         * </summary>
         */
        protected bool CreatePath(Machine<Stream>.IState beginNode, Machine<Stream>.IState endNode,
            string s, ref int i, int end)
        {
            StringBuilder local = new StringBuilder();
            Arrow arrow;
            Arrow.Type type = Arrow.Type.Unkown;
            CharSet charset = null;
            Machine<Stream>.Iteration iteration;
            Char ch = new Char();
            TagTracker tag = null;
            Machine<Stream>.IState lastNode = beginNode;

            for (int p = i; p < end; )
            {
                if (s[p] == '[')
                {
                    if (!GetCharSet(out charset, s, ref p, end))
                    {
                        i = p;
                        return false;
                    }
                    type = Arrow.Type.CharSetChar;
                }
                else if (s[p] == '.')
                {
                    p++;
                    type = Arrow.Type.AnyChar;
                }
                else if (s[p] == '\\')
                {
                    int itry = p;
                    itry++;
                    if (s[itry] == 'k')
                    {
                        p = itry;
                        p++;    // 'i; is now expected to be at '<'
                        if (!GetTag(out tag, s, ref p, end))
                        {
                            i = p;
                            return false;
                        }
                        type = Arrow.Type.Tag;
                    }
                    else
                    {
                        if (!GetEscape(out ch, s, ref p, end))
                        {
                            i = p;
                            return false;
                        }
                        type = Arrow.Type.CommonChar;
                    }
                }
                else
                {   /* plain character */
                    ch = s[p++];
                    type = Arrow.Type.CommonChar;
                }

                if (p < end && (s[p] == '{' || s[p] == '*' || s[p] == '+'))
                {   
                    /* spawn a trap-state node */
                    Machine<Stream>.TrapState trapNode = new Machine<Stream>.TrapState();

                    if (!GetIteration(out iteration, s, ref p, end))
                    {
                        i = p;
                        return false;
                    }
                    trapNode.Iteration = iteration;

                    StringArrow stringArrow = new StringArrow(local.ToString());
                    stringArrow.Link(lastNode, trapNode);

                    arrow = null;
                    if (type == Arrow.Type.CommonChar)
                        arrow = new CharArrow(ch);
                    else if (type == Arrow.Type.CharSetChar)
                        arrow = new CharSetArrow(charset);
                    else if (type == Arrow.Type.AnyChar)
                        arrow = new AnyCharArrow();
                    else if (type == Arrow.Type.Tag)
                        arrow = new TagArrow(tag);
                    else
                        throw new InvalidOperationException();

                    arrow.Link(trapNode, trapNode);

                    lastNode = trapNode;

                    local = new StringBuilder();    // set to ""
                }
                else
                {
                    if (type == Arrow.Type.CommonChar)
                    {
                        local.Append(ch);

                        if (p >= end)
                        {
                            if (local.Length == 1) 
                                arrow = new CharArrow(ch);
                            else 
                                arrow = new StringArrow(local.ToString());
                            arrow.Link(lastNode, endNode);
                            return true;
                        }
                    }
                    else if (type == Arrow.Type.CharSetChar || type == Arrow.Type.AnyChar)
                    {
                        if (local.Length > 0)
                        {
                            /* spawn a relay-state node */
                            Machine<Stream>.RelayState relayNode = new Machine<Stream>.RelayState();
                            arrow = new StringArrow(local.ToString());
                            arrow.Link(lastNode, relayNode);
                            lastNode = relayNode;
                            local = new StringBuilder();
                        }

                        Machine<Stream>.IState node;
                        if (p < end)
                            node = new Machine<Stream>.RelayState();
                        else
                            node = endNode;

                        if (type == Arrow.Type.CharSetChar)
                            arrow = new CharSetArrow(charset);
                        else
                            arrow = new AnyCharArrow();

                        arrow.Link(lastNode, node);

                        if (p >= end)
                            return true;

                        lastNode = node;
                    }
                    else if (type == Arrow.Type.Tag)
                    {
                        if (local.Length > 0)
                        {
                            /* spawn a relay-state node */
                            Machine<Stream>.RelayState relayNode = new Machine<Stream>.RelayState();
                            arrow = new StringArrow(local.ToString());
                            arrow.Link(lastNode, relayNode);
                            lastNode = relayNode;
                            local = new StringBuilder();
                        }

                        if (p >= end)
                        {
                            arrow = new TagArrow(tag);
                            arrow.Link(lastNode, endNode);
                            return true;
                        }

                        Machine<Stream>.RelayState node = new Machine<Stream>.RelayState();
                        arrow = new TagArrow(tag);
                        arrow.Link(lastNode, node);

                        lastNode = node;
                    }
                }
            }

            arrow = new StringArrow(local.ToString());
            arrow.Link(lastNode, endNode);

            return true;
        }

        protected bool Preparse(out List<int> coil, string s, ref int i, int end)
        {
            coil = new List<int>();

            int begin;
            bool bInCharSet = false;
            int nParentheses = 0;
            char ch;

            for (; i < end; i++)
            {
                if (s[i] == '\\')
                {
                    i++;
                    if (i >= end) break;
                    continue;
                }

                if (s[i] == '[')
                {
                    bInCharSet = true;
                    continue;
                }
                if (bInCharSet)
                {
                    if (s[i] == ']') bInCharSet = false;
                    continue;
                }

                if (s[i] == '(')
                {
                    coil.Add(i);
                    nParentheses++;
                }
                else if (s[i] == ')')
                {
                    begin = i;
                    if (nParentheses <= 0 || coil.Count == 0)
                    {   // ')' is not expected
                        return false;
                    }

                    nParentheses--;

                    ++i;

                    if (i >= end)
                    {
                        coil.RemoveAt(coil.Count - 1);
                        i = begin;
                    }
                    else
                    {
                        ch = s[i];
                        if (ch != '{' && ch != '*' && ch != '+')
                        {
                            coil.RemoveAt(coil.Count - 1);
                            i = begin;
                        }
                    }
                }
            }

            begin = i;
            return (nParentheses == 0);
        }

        protected bool TagOpen(Machine<Stream>.TagOpenState beginNode, string s, ref int i, int end)
        {
            string sTag;

            // tag number starts from 1
            if (mUseNumericTag)
                mTagCount++;

            if (s[i] == '?')
            {
                i++;

                if (i >= end || s[i] != '<') return false;
                i++;

                int iTagNameBegin = i;

                for (; i < end && s[i] != '>'; i++)
                {
                }

                if (i >= end) return false;

                int iTagNameEnd = i;
                i++;

                sTag = s.Substring(iTagNameBegin, iTagNameEnd - iTagNameBegin);
            }
            else if (mUseNumericTag)
            {
                sTag = mTagCount.ToString();
            }
            else
            {
                return true;
            }

            TagCreator tagCreator = mTagMapper[sTag];
            if (tagCreator == null)
            {
                tagCreator = new TagCreator() { Tracker = new TagTracker() };
                mTagMapper[sTag] = tagCreator;
            }

            mTagStack.Push(tagCreator);

            // tag it on the node
            beginNode.Tag = tagCreator.Tracker;

            return true;
        }

        protected bool TagClose(Machine<Stream>.TagOpenState beginNode, Machine<Stream>.TagCloseState endNode)
        {
            if (mTagStack.Count == 0)
                return true;

            // tag it on the node
            TagCreator tagCreator = mTagStack.Pop();
            endNode.Tag = tagCreator.Tracker;
            tagCreator.Closed = true;

            return true;
        }

        public Machine<Stream> Create(string s)
        {
            int end = s.Length;
            int i = 0;

            mTagMapper.Clear();
            mTagStack.Clear();

            ParsingState cur;

            List<int> coil;
            int begin = i;
            if (!Preparse(out coil, s, ref i, end))
                throw new Exception(i);

            int iCoil = 0;
            bool bInCharSet = false;

            /* spawn the starting node */
            Machine<Stream>.IState startNode = new Machine<Stream>.RelayState();
            Machine<Stream>.IState lastNode = startNode;
            Machine<Stream>.TagOpenState lpNode;
            Machine<Stream>.TagCloseState rpNode;

            cur.BeginNode = startNode;
            cur.EndNode = null;

            Stack<ParsingState> stk = new Stack<ParsingState>();
            stk.Push(cur);

            i = begin;
            int p = i;
            int lastp = i;
            int dst;

            for ( ; p < end; )
            {
                if (s[p] == '\\')
                {
                    p++;
                    if (p >= end) break;
                    p++;
                    continue;
                }

                if (s[p] == '[')
                {
                    p++;
                    bInCharSet = true;
                    continue;
                }

                if (bInCharSet)
                {
                    if (s[p] == ']')
                    {
                        bInCharSet = false;
                    }
                    p++;
                    continue;
                }

                if (s[p] == '(')
                {
                    if (iCoil != coil.Count && coil[iCoil] == p)
                    {
                        /**
                         * <remarks>
                         *                  ...
                         *                )       (
                         *            rpNode    lpNode
                         *                 \    /        
                         *  lastNode -> cur.BeginNode -> 
                         *              /cur.EndNode
                         *               
                         * </remarks>
                         */

                        /* to spawn a repetitive node */
                        Machine<Stream>.TrapState trap = new Machine<Stream>.TrapState();

                        lpNode = new Machine<Stream>.TagOpenState();
                        rpNode = new Machine<Stream>.TagCloseState();

                        /* connect trap to lpNode with an empty arrow */
                        CreatePath(trap, lpNode, s, ref p, p);

                        /* connect rpNode to trap with an empty arrow */
                        CreatePath(rpNode, trap, s, ref p, p);

                        iCoil++;

                        dst = p;
                        i = lastp;
                        if (!CreatePath(lastNode, trap, s, ref i, dst))
                        {
                            throw new Exception(i);
                        }

                        lastNode = cur.BeginNode = lpNode;
                        cur.EndNode = rpNode;
                    }
                    else
                    {
                        /**
                         * <remarks>
                         *                   ...
                         *                    (        
                         *  lastNode -> cur.BeginNode  ... -> cur.EndNode(null)
                         *                /lpNode
                         * </remarks>
                         */

                        /* to spawn an forward node */
                        cur.BeginNode = lpNode = new Machine<Stream>.TagOpenState();
                        cur.EndNode = null; /* left for future assignment */

                        /* lastp is moved to p if successful */

                        dst = p;
                        i = lastp;

                        if (!CreatePath(lastNode, cur.BeginNode, s, ref i, dst))
                        {
                            throw new Exception(i);
                        }

                        lastNode = cur.BeginNode;
                    }

                    p++;    // to have it excluded from path creation

                    if (!TagOpen(lpNode, s, ref p, end))
                    {
                        throw new Exception(i);
                    }

                    lastp = p;
                    stk.Push(cur);
                }
                else if (s[p] == ')')
                {
                    cur = stk.Pop();
                    System.Diagnostics.Debug.Assert(stk.Count > 0);

                    dst = p;
                    p++;
                    if (p < end && (s[p] == '{' || s[p] == '*' || s[p] == '+'))
                    {   /* iterative, the closing node is just the opening one */
                        /**
                         *                ...
                         *            /       \
                         *       lastNode
                         *          |
                         *       rpNode/       lpNode/
                         *    cur.EndNode  cur.BeginNode
                         *            \      / 
                         *              trap  ->
                         */

                        Machine<Stream>.TrapState trap = cur.EndNode.GetOutlet(0).Target as Machine<Stream>.TrapState;
                        Machine<Stream>.Iteration iteration;

                        /* p will be moved to the position right after the iteration descriptor */
                        if (!GetIteration(out iteration, s, ref p, end))
                        {
                            throw new Exception(i);
                        }


                        trap.Iteration = iteration;

                        lpNode = cur.BeginNode as Machine<Stream>.TagOpenState;
                        rpNode = cur.EndNode as Machine<Stream>.TagCloseState;

                        i = lastp;

                        if (!CreatePath(lastNode, cur.EndNode, s, ref i, dst))
                        {
                            throw new Exception(i);
                        }

                        lastNode = trap;
                    }
                    else
                    {   /* non-iterative */

                        /** 
                         *                   ( ... )
                         *       rpNode/    -> ... ->     lpNode/
                         *    cur.EndNode               cur.BeginNode
                         *                           (may need to be created
                         *                            depending on if it's 
                         *                            closing a fanout)
                         */

                        if (cur.EndNode == null)
                        {
                            /* spawn a closing node */
                            cur.EndNode = new Machine<Stream>.TagCloseState();
                        }

                        i = lastp;
                        if (!CreatePath(lastNode, cur.EndNode, s, ref i, dst))
                        {
                            throw new Exception(i);
                        }

                        lpNode = cur.BeginNode as Machine<Stream>.TagOpenState;
                        rpNode = cur.EndNode as Machine<Stream>.TagCloseState;

                        lastNode = cur.EndNode;
                    }

                    if (!TagClose(lpNode, rpNode))
                    {
                        begin = dst;
                        throw new Exception(i);
                    }

                    lastp = p;

                    /* load the context from the stack top */
                    cur = stk.Peek();
                }
                else if (s[p] == '|')
                {
                    if (cur.EndNode == null)
                    {
                        /** 
                         *              -> ... lastNode \
                         *            /                  \
                         *   cur.Begin -..          cur.EndNode 
                         *  /nextLastNode         (to be created)
                         * 
                         */
                        if (cur.BeginNode == startNode)
                        {   /* it's now on the main path */
                            cur.EndNode = new Machine<Stream>.TerminalState();
                        }
                        else
                        {
                            cur.EndNode = new Machine<Stream>.TagCloseState();
                        }

                        // update the parsing-state on the top
                        ParsingState ps = stk.Pop();
                        ps.EndNode = cur.EndNode;
                        stk.Push(ps);
                    }
                    else
                    {
                        /**
                         *           lastNode ... \
                         *            / 
                         *            )             (
                         *      cur.EndState   cur.BeginState
                         *             \           /
                         *                 trap/    -> ...
                         *             nextLastNode
                         */

                        System.Diagnostics.Debug.Assert(cur.EndNode is Machine<Stream>.TagCloseState);
                        System.Diagnostics.Debug.Assert(cur.EndNode.GetOutlet(0).Target is Machine<Stream>.TrapState);

                    }

                    dst = p;
                    i = lastp;

                    if (!CreatePath(lastNode, cur.EndNode, s, ref i, dst))
                    {
                        throw new Exception(i);
                    }

                    p++;
                    lastp = p;
                    lastNode = cur.BeginNode;
                }
                else
                {
                    p++;
                }
            }   /* for */

            cur = stk.Pop();

            System.Diagnostics.Debug.Assert(stk.Count == 0);

            dst = p;
            i = lastp;

            /* finish last node */

            if (cur.EndNode == null)
            {
                cur.EndNode = new Machine<Stream>.TerminalState();
            }

            CreatePath(lastNode, cur.EndNode, s, ref i, dst);

            Machine<Stream> machine = new Machine<Stream>(startNode, cur.EndNode);

            return machine;
        }
    }   /* class 3 */

}   /* namespace QSharp.String.Rex */

